package com.xyhuo.leetcode.december;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 括号生成
 * https://leetcode.cn/problems/generate-parentheses/
 *
 * @time 2023/12/8
 */
public class GenerateParenthesis {

//    public static void main(String[] args) {
//        GenerateParenthesis gp = new GenerateParenthesis();
//        gp.generateParenthesis(5);
//    }

    public List<String> generateParenthesis(int n) {

        Set<String>[] dp = new Set[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashSet<>();
        }
        dp[0].add("()");
        for (int i = 1; i < n; i++) {
            for (String item : dp[i - 1]) {
                dp[i].add("(" + item + ")");
            }
            int half = i / 2 + 1;
            for (int j = 0; j < half; j++) {
                for (String s : dp[j]) {
                    for (String s1 : dp[i - 1 - j]) {
                        dp[i].add(s + s1);
                        dp[i].add(s1 + s);
                    }
                }
            }
        }

        return dp[n - 1].stream().collect(Collectors.toList());
    }
}
